COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Chapter 2: An example 
C00004 00003	Chapter 2: An example 
C00019 ENDMK
C⊗;
Chapter 2: An example 

a) Open with a good, 2-page example, a sample excerpt of a session with AM
Tentative choice: find examples of =, need to generalize =, discover "numbers"

b) Explain the example in more and more detail, 
   but always in English/Math terms; even though it will be necessary to
   delve into the system's reasoning deeper and deeper, that too should
   always remain informal, in English/Math. Don't worry about representation,
   mechanism to pass control, etc.

  e.g., we may say "when so few exs are found, it is natural to try to generalize
  the predicate in question", without describing the precise way that heuristic is
  stored, or how it accomplishes its action-part, or how it gets considered in the
  first place. All THOSE things will be dealt with in chapter 5 (detailed examples)

  e.g., we'll say "one way to fill in examples of a predicate is to find some
  exs of its domain, then randomaly pick as many as are required, then run the
  predicate and see if the result is T or F". We may want to go into detail about
  finding out the domain of the predicate, getting examples of the domain, etc., 
  but probably not at the level of GETP(EQUALITY DOMAIN) or GETP(SETS EXAMPLES).

Chapter 2: An example 

Here is a typical trace of AM in action. Recall that although AM uses
many of the plausible reasoning rules which mathematicians use, its
initial base of known concepts is quite small. Below, AM knows a little
about sets and lists (e.g., equality), but has never heard anything about size,
arithmetic, etc. The excerpt shows how and why AM encounters concepts which we 
call: same-length, size, number, multiplication, and square-root.

**********************************************************************
I am now filling in examples of the predicate "Equality".
  3 Reasons:
    1) No examples of "Equality" have ever been filled in.
    2) The interest factor of "Equality" increased recently
    3) The interest factor of "Equality" is now very high

  By instantiating a recursive definition of "Equality", I have produced
	a few examples: T=T, NIL=NIL, (NIL)=(NIL).
  I will now try to run "Equality" on randomly-chosen arguments.
  	The Domain of this predicate is: Pairs of Objects.
	I know many objects, and repeatedly pick a pair of them and 
		run "Equality" on them, noting the result.
	Out of 155 trials, only 4 pairs of objects turned out to satisfy "Equality".
		This ratio (4/155) is too low; it indicates that "Equality" is
		too specialized, too narrow. I suggest generalizing "Equality".
  In all, 8 examples of this predicate were found.

**********************************************************************

I am now trying to generalize the predicate "Equality"
  2 Reasons:
    1) No generalizations of "Equality" have ever been filled in.
    2) Empirical evidence suggests that "Equality" is very rarely satisfied.

  The first definition of "Equality" is opaque. Failure.
  The second definition of "Equality" is recursive. I will look closer.
	It consists of a base step, and two conjoined recursive calls:

		EQUALITY(X,Y) iff
			IF X and Y are both empty, then T
			ELSE, IF X and Y are both nonempty, then both
				EQUALITY( CAR(X), CAR(Y) ), and
				EQUALITY( CDR(X), CDR(Y) ).

	
	There are several easy ways to generalize this definition.
	I could replace the conjunction( AND) by a disjunction (OR).
	I could replace either of the recursions by the constant T.
	These lead to 3 apparently distinct generalizations.
	A secondary generalization would be to conjoin or disjoin THEM, etc.

	Here, for example, is the new predicate which is the result of
	replacing the first recursion by T; i.e., the predicate now will
	recur only in the CDR direction:

		GENL-EQ(X,Y) iff
			IF X and Y are both empty, then T
			ELSE, IF X and Y are both nonempty, then both
				T  and
				GENL-EQ( CDR(X), CDR(Y) ).


USER: Call this new predicate "Same-length".


**********************************************************************

I am now filling in examples of the predicate "Same-length".
  3 Reasons:
    1) No examples of "Same-length" have ever been filled in.
    2) Hope that "Same-length" will be satisfied more easily than "Equality"
    3) Working on "Same-length" now will preserve focus of attention

  By instantiating a recursive definition of "Same-length", I have produced
	a few examples: T=T, T=NIL, (T)=(NIL).
  I will now try to run "Same-length" on randomly-chosen arguments.
  	The Domain of this predicate is: Pairs of Objects.
	I know many objects, and repeatedly pick a pair of them and 
		run "Same-length" on them, noting the result.
	Out of 155 trials, 26 pairs of objects turned out to satisfy "Same-length".
		This ratio (26/155) is quite nice. Especially compared to "Equality".
  In all, 30 examples of this predicate were found. 3 duplicates were eliminated.

**********************************************************************

I am now trying to find a canonical form for objects satisfying "Same-length".
That is, I hope to find a function f, such that
  f(x)=f(y) precisely when x and y satisfy Same-length.

  6 Reasons:
    1) For any interesting predicate P, try to canonize genl(P) with respect to P.
	In this case, P="Equality", and genl(P)="Same-length".
    2) If successful, we can use the fast algorithm for Equality, instead of
	the empirically slower algorithm now known for computing Same-length.
    3) Working on "Same-length" now will preserve focus of attention
    4) The interest factor of "Same-length" increased recently
    5) The interest factor of "Same-length" is now very high
    6) The interest factor of "Equality" is still very high

  I shall find f by performing various experiments on Same-length (and Equality).

  Experiment #1: 
	Is Same-length affected by the type of object involved?
	For example, is Same-length((Vector a)(Vector b))=
			Same-length((Class a)(Class b)) ?
	Empirically, no affect.
	So a single, "caonical" type of argument can be fixed once and for all.
	The four kinds of arguments are Class, List, Ordered-set, Bag.

  Experiment #2:
	Is Same-length affected by changing the order of elements in its arguments?
	For example, is Same-length((Vector a b),(Vector a b))=
			Same-length((Vector b a),(Vector a b)) ?
	Empirically, no affect.
	So the "canonical" kind of argument is an unordered type (Bag or Set).

  Experiment #3:
	Is Same-length affected by adding multiple elements to its arguments?
	For example, is Same-length((Vector a b),(Vector a b))=
			Same-length((Vector a b b),(Vector a b)) ?
	Empirically, there is an affect! 
	So the "canonical" kind of argument must recognize multiple copies of the
		same element. So it must be either Bag or List.
	Based on the previous experiment, the canonical type must be Bag.

  Experiment #4:
	A note stored under the concept "Same-length" says that this is very
		similar to "Equaility", but it doesn't recurse in the CAR direction.
	But the values of atoms are stored in their CARs.
	Thus it is worth seeing if in fact Same-length ever accesses the value
		cells of its arguments.
	For example, is Same-length((Vector a b),(Vector a b))=
			Same-length((Vector c d),(Vector a b)) ?
	Empirically, there is no affect! 
	So the "canonical" kind of argument can have only a single, fixed allowable
		element, say the constant element T.
	Based on the previous experiment, the canonical type must be Bag of all T's.

  Tentatively, the function f will do the following things:
	Take any object, convert it to a BAG, replace each element by T.



USER: Call this function "Size". Call the canonical bags "numbers".


  There is a powerful analogy between:
		Same-size................Equality
		Numbers..................Objects
  In particular, all the interesting operators whose Domain/Range involves
	Bags, can now be considered restricted to Numbers.


**********************************************************************


I am now restricting the operation "Cross-product" to the domain "Numbers".
  1 Reason:
    1) Exploit the analogy between Same-size and Equality, for 2 reasons:
	a) Generate interesting new concepts, perhaps.
	b) Use the efficiency of Equality's definition to speed-up Cross-product's.
    2) Complete the square diagram:
	2 Bags →→→→→→→→→→→→(size)→→→→→→→→→→→→ 2 Numbers
	  ↓					 ↓
	  ↓					 ↓
	  ↓cross-product			 ↓ ?
	  ↓					 ↓
	  ↓					 ↓
	1 Bag →→→→→→→→→→→→→(size)→→→→→→→→→→→→ 1 Number


  Creating a new operation, f, analogous to Cross-product.
  Its domain is a pair of numbers, and its range is a number.
  Note that since each Number is a special kind of Bag, the operation
	Cross-product can operate on a pair of numbers.
  A crude definition of f is Size(Cross-product(x,y)).
  Some examples of f are as follows:
  	f((Bag T T T T) (Bag T T T)) = (Bag T T T T T T T T T T T T)
  	f((Bag T T T) (Bag T )) = (Bag T T T)
  	f((Bag T T) (Bag T T)) = (Bag T T T T)
  	f((Bag) (Bag T T)) = (Bag)

USER: Call this operation "Multiply".
Give the names 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, to the following numbers:
(Bag), (Bag T), (Bag T T), (Bag T T T),..., (Bag T T T T T T T T T).

**********************************************************************

I am now coalescing the operation Multiply.
  3 Reasons:
    1) The interest factor of Multiply is very high.
    2) Working on Multiply would preserve focus of attention
    3) The domain of Multiply consists of 2 arguments of the same type

  Creating new operation, Coa-Multiply, defined as Multiply(x,x).
  Its domain is a number, and its range is a number.
  Some examples of Coa-Multiply are as follows:
	Coa-Multiply(2) = 4
	Coa-Multiply(0) = 0
	Coa-Multiply(3) = 9
	Coa-Multiply(4) = (Bag T T T T T T T T T T T T T T T T)


USER: Call this operation "Squaring". Any number in its range is a "Square".


**********************************************************************

I am now considering finding the operation which is the inverse of Squaring.
  3 Reasons:
    1) This operation would be the only one to have as its domain the new
	concept Square-numbers.
    2) Squaring is interesting, so its inverse may be interesting.
    3) Working with Squaring now would preserve focus of attention.